907. Sum of Subarray Minimums.go

package leetcode

// 解法一 最快的解是 DP + 单调栈
funcsumSubarrayMins(A []int) int {
stack, dp, res, mod:= []int{}, make([]int, len(A)+1), 0, 1000000007
stack=append(stack, -1)

fori:=0; i<len(A); i++ {
forstack[len(stack)-1] !=-1&&A[i] <=A[stack[len(stack)-1]] {
stack=stack[:len(stack)-1]
 }
dp[i+1] = (dp[stack[len(stack)-1]+1] + (i-stack[len(stack)-1])*A[i]) %mod
stack=append(stack, i)
res+=dp[i+1]
res%=mod
 }
returnres
}

typepairstruct {
valint
countint
}

// 解法二 用两个单调栈
funcsumSubarrayMins1(A []int) int {
res, n, mod:=0, len(A), 1000000007
lefts, rights, leftStack, rightStack:=make([]int, n), make([]int, n), []*pair{}, []*pair{}
fori:=0; i<n; i++ {
count:=1
forlen(leftStack) !=0&&leftStack[len(leftStack)-1].val>A[i] {
count+=leftStack[len(leftStack)-1].count
leftStack=leftStack[:len(leftStack)-1]
 }
leftStack=append(leftStack, &pair{val: A[i], count: count})
lefts[i] =count
 }

fori:=n-1; i>=0; i-- {
count:=1
forlen(rightStack) !=0&&rightStack[len(rightStack)-1].val>=A[i] {
count+=rightStack[len(rightStack)-1].count
rightStack=rightStack[:len(rightStack)-1]
 }
rightStack=append(rightStack, &pair{val: A[i], count: count})
rights[i] =count
 }

fori:=0; i<n; i++ {
res= (res+A[i]*lefts[i]*rights[i]) %mod
 }
returnres
}

// 解法三 暴力解法，中间很多重复判断子数组的情况
funcsumSubarrayMins2(A []int) int {
res, mod:=0, 1000000007
fori:=0; i<len(A); i++ {
stack:= []int{}
stack=append(stack, A[i])
forj:=i; j<len(A); j++ {
ifstack[len(stack)-1] >=A[j] {
stack=stack[:len(stack)-1]
stack=append(stack, A[j])
 }
res+=stack[len(stack)-1]
 }
 }
returnres%mod
}